package com.currentbp.Interesting.likou.complete;

import org.junit.Test;

/**
 * @author baopan
 * @createTime 2024/3/18 21:14
 */
public class T1526minNumberOperations {
    /*
给你一个整数数组 target 和一个数组 initial ，initial 数组与 target  数组有同样的维度，且一开始全部为 0 。
请你返回从 initial 得到  target 的最少操作次数，每次操作需遵循以下规则：
在 initial 中选择 任意 子数组，并将子数组中每个元素增加 1 。
答案保证在 32 位有符号整数以内。
示例 1：
输入：target = [1,2,3,2,1]
输出：3
解释：我们需要至少 3 次操作从 intial 数组得到 target 数组。
[0,0,0,0,0] 将下标为 0 到 4 的元素（包含二者）加 1 。
[1,1,1,1,1] 将下标为 1 到 3 的元素（包含二者）加 1 。
[1,2,2,2,1] 将下表为 2 的元素增加 1 。
[1,2,3,2,1] 得到了目标数组。
示例 2：
输入：target = [3,1,1,2]
输出：4
解释：(initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target) 。
示例 3：
输入：target = [3,1,5,4,2]
输出：7
解释：(initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1]
                                  -> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target)。
示例 4：
输入：target = [1,1,1,1]
输出：1
     */
    @Test
    public void t1() {
        System.out.println(minNumberOperations2(new int[]{1, 2, 3, 2, 1}));
        System.out.println(minNumberOperations2(new int[]{3, 1, 1, 2}));
        System.out.println(minNumberOperations2(new int[]{3, 1, 5, 4, 2}));
        System.out.println(minNumberOperations2(new int[]{1, 1, 1, 1}));
    }

    /*
    解题思路2：
    1、假若整个数组的格式是[[a,x,b][c,y,d][e,z,f]],其中x，y，z都是最高点
    2、对于一个小数组[a,x,b]而言，只需要执行次数是a+（x-a）次就行，因为b会被覆盖了
    3、只需要计算两个数的大小，[0,a,x,b]，最大数x后面的都算0
     */
    public int minNumberOperations2(int[] target) {
        if (target == null || target.length < 1) {
            return 0;
        }
        if (target.length == 1) {
            return target[0];
        }
        int result = target[0];
        int before = target[0];
        for (int index = 0; index < target.length; index++) {
            if (before < target[index]) {
                result += (target[index] - before);
                before = target[index];
            } else {
                before = target[index];
            }
        }

        return result;
    }

    /*
    解题思路：
    1、在区间a-b之间找出最小数x，直接将这个区间的所有数字全部减去x，次数+1
    2、以x的index作为分界线，左区间[a,x-1], 右区间[x+1,b]
    3、对每一个小区间做重复的事件
    4、其中，如果遇到最小数为0，则按照小区间分割，不加次数
     */
    //这个方案超时了
    public int minNumberOperations(int[] target) {
        if (target == null || target.length < 1) {
            return 0;
        }
        if (target.length == 1) {
            return target[0];
        }

        return doEach(target, 0, target.length - 1);
    }

    private int doEach(int[] target, int start, int end) {
        if (start > end) {
            return 0;
        }

        int min = target[start];
        int minIndex = start;
        for (int i = start; i <= end; i++) {
            if (target[i] < min) {
                min = target[i];
                minIndex = i;
            }
        }

        for (int i = start; i <= end; i++) {
            target[i] -= min;
        }
        return min + doEach(target, start, minIndex - 1) + doEach(target, minIndex + 1, end);
    }
}
